package main.剑指OfferⅠ;

public class Day14 {
    public static void main(String[] args) {
        System.out.println("剑指Offer12.矩阵中的路径");
        System.out.println("剑指Offer13.机器人的运动范围");
        System.out.println(new Offer13().movingCount(16,8,4));
    }
}

class Offer12{
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n;
    char[][] board;
    String word;
    boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        this.m = board.length;
        this.n = board[0].length;
        this.board = board;
        this.word = word;
        this.visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (backtrack(i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean backtrack(int row, int col, int index) {
        if (index == word.length()) {
            return true;
        }
        if (row < 0 || row >= m || col < 0 || col >= n || visited[row][col] || board[row][col] != word.charAt(index)) {
            return false;
        }
        visited[row][col] = true;
        boolean found = false;
        for (int[] dir : dirs) {
            int newRow = row + dir[0], newCol = col + dir[1];
            found = backtrack(newRow, newCol, index + 1);
            if (found) {
                break;
            }
        }
        visited[row][col] = false;
        return found;
    }
}

class Offer13{
    int count=0;
    boolean[][] arr;
    public int process1(int r,int c){
        int sum=0;
        char[] num1=String.valueOf(r).toCharArray(),num2=String.valueOf(c).toCharArray();
        for (char c1:num1) sum+=c1-'0';
        for (char c1:num2) sum+=c1-'0';
        return sum;
    }
    public void process2(int r,int c,int k){
        int m= arr.length,n=arr[0].length;
        if (process1(r,c)<=k) {
            arr[r][c]=true;
            count++;
        }
        if (r-1>=0&&arr[r-1][c]==false&&process1(r-1,c)<=k) process2(r-1,c,k);//上
        if (r+1<m&&arr[r+1][c]==false&&process1(r+1,c)<=k) process2(r+1,c,k);//下
        if (c-1>=0&&arr[r][c-1]==false&&process1(r,c-1)<=k) process2(r,c-1,k);//左
        if (c+1<n&&arr[r][c+1]==false&&process1(r,c+1)<=k) process2(r,c+1,k);//右
    }
    public int movingCount(int m, int n, int k) {
        arr=new boolean[m][n];
        process2(0,0,k);
        return count;
    }
}